package ua.yandex.collections;

import java.util.Comparator;

public class MyCollections {

  public static void reverse(MyList list) {
    Object lastVal;
    int lastIndex = list.size() - 1;
    for (int i = 0; i < list.size() - 1; i++) {
      lastVal = list.get(lastIndex);
      list.remove(lastIndex);
      list.add(i, lastVal);
    }
  }

  public static int binarySearch(MyList list, Object key) {
    CmpList cp = new CmpList();
    return binarySearch(list, key, cp, 0, list.size() - 1);
  }
  
  public static int binarySearch(MyList list, Object key, Comparator cp) {
    return binarySearch(list, key, cp, 0, list.size() - 1);
  }
  
  private static int binarySearch(MyList list,
                                  Object key,
                                  Comparator cp,
                                  int f,  int l) {
    if (f == l) {
      if (cp.compare(list.get(f), key) == 0) {
        return f;
      } else if (cp.compare(list.get(f), key) > 0) {
        return -f - 1;
      } else {
        return -(f+1) - 1;
      }
    } else {
      int delta = (l - f) / 2;
      if (cp.compare(list.get(f + delta), key) > 0)
      {
        return binarySearch(list, key, cp, f, f + delta);
        
      } else if (cp.compare(list.get(f + delta), key) < 0) {
        return binarySearch(list, key, cp, f + delta + 1, l);
      } else {
        return f + delta;
      }
    }
  }
  
  static class CmpList implements Comparator {
    
    @Override
    public int compare(Object a, Object b) {
      return ((Comparable) a).compareTo((Comparable) b);
    }
    
  }
  
}
